Cannon's algorithm
In computer science, Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes first described in 1969 by Lynn Elliot Cannon.[1][2]
It is especially suitable for computers laid out in an N × N mesh.[3] While Cannon's algorithm works well in homogeneous 2D grids, extending it to heterogeneous 2D grids has been proven to be difficult.[4]
The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.[2]
See also
References
- ^ Lynn Elliot Cannon, A cellular computer to implement the Kalman Filter Algorithm, Technical report, Ph.D. Thesis, Montana State University, 14 July 1969.
- ^ a b Gupta, H.; Sadayappan, P.: Communication Efficient Matrix-Multiplication on Hypercubes, dbpubs.stanford.edu
- ^ 4.2 Matrix Multiplication on a Distributed Memory Machine, ipp.mpg.de
- ^ Research, graal.ens-lyon.fr
External links
|
|
|
| Key concepts |
|
|
| Problems |
|
|
| Hardware |
|
|
| Software |
|
|
‹The stub template below has been proposed for renaming to . See stub types for deletion to help reach a consensus on what to do.
Feel free to edit the template, but the template must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, read the guide to deletion.›